Packet transmission networks have become common for providing communications between data processing centers as well as other communications users. Packet transmission systems comprise a plurality of packet switching nodes interconnected with transmission links. Such transmission systems divide digital information into a plurality of packets having a header with all of the routing information necessary to control the switching nodes in order to move the packet from the originating node to the destination node. Packet networks were originally created on a local level for servicing closely clustered data processing sites. Increasingly, however, packet networks are being used for large, widely distributed data processing sites which may be not only national, but international in scope.
Several different routing protocols have been used to control the routing of packets from node to node through a packet transmission system. Such protocols include the so-called "swap" protocol in which the label in the packet header is used as a look-up address in a table to determine the next leg of the route. Automatic Network Routing (ANR) uses a concatenation of link labels to identify the successive legs of the route, which labels are stripped away one at a time as the packet traverses the network, always leaving the next-to-be-used label at the head of the routing field. Another such routing protocol, called "tree multicast routing," is the subject matter of the present invention. In this routing protocol, a tree is defined as a connected set of network nodes and links having no cycles or loops. The term "multicast" means that a single sender transmits the same packets to a multiplicity of receiving nodes. Such a multicast tree utilizes a tree address in the routing field of the packet header. The same tree address is associated with each transmission link forming part of the multicast tree. When a multicast packet reaches a packet switching node, the tree address in the packet header is compared to the tree addresses associated with all of the outgoing transmission links from that node. If a match occurs, the packet is forwarded on the transmission links for which the match occurs, except for the link on which the packet is received. It will be noted that multiple copies of the packet may be generated at each switching node to accommodate multicast trees having multiple branches at the switching node.
Multicast tree routing has become a common method of communicating over a packet transmission system due to the efficiencies of the multicast tree protocol. It will be noted that such multicast tree routing can be used for the distribution of packets to all nodes of a communication network and involves the determination and maintenance of the optimum path (the spanning tree) for connecting the nodes with each other. It has been common in the prior art to create and use multicast spanning trees for this purpose. Considerable problems arise, however, if nodes are added or removed from the network or if hardware failures and reactivation cause partition of the tree or the creation of cycles in the spanning tree. The reliable distribution of multicast messages in a constantly changing tree structure is the subject matter of the present invention.
Prior art methods for reliable distribution of multicast messages across a spanning tree involved the sending node storing the message until acknowledgments are received from each receiving station on the spanning tree, and retransmitting the message to those receiving stations not acknowledging reception. However, because the network is not static and nodes may join or leave the network, the sender does not always know how many nodes are in the tree nor how many acknowledgments are to be expected for each message sent. Moreover, if the network becomes partitioned due to the failure of a node or a link, it is impossible to ensure consistency of information transfer to all nodes in the network or even to all nodes within a given partition of the network. This is particularly important when a multicast spanning tree is used to route network topology information to all nodes of a network, and consistent views of the network topology are required for accurate routing of data packets.